
有穷自动机 非确定性 正则运算 正则表达式 非正则语言
例20 (y²C = {ww|w ∈ {0, 1}
∗
}Ø´Kó)
y: bC´K,p´ÙA"长Ý。 ÄiÎ
Gs = 0
p
10
p
1 ∈ C,s = xyz为3"引理e©ã,K
du|xy| ≤ p, |y| > 0,Ky = 0
t
, t ≤ p
ddxyyz 6∈ C
例21 (y²D = {0
i
1
j
|i > j}Ø´Kó)
y: bD´K,p´ÙA"长Ý。 ÄiÎ
Gs = 0
p+1
1
p
∈ D,s = xyz为3"引理e©ã,K
du|xy| ≤ p, |y| > 0,Ky = 0
t
, 0 < t ≤ p
ddxy
0
z = xz 6∈ D
吴 铤 杭州电子科技大学络空间安全学院
Kó